"""
27. 移除元素
https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150
"""
from typing import List


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # step = 0
        # for i in range(len(nums)):
        #     if nums[i] == val:
        #         continue
        #     nums[step] = nums[i]
        #     step += 1
        # return step
        """
        双指针
        """
        n = len(nums)
        left = 0
        for right in range(n):
            if nums[right] != val:
                nums[left] = nums[right]
                left += 1
        return left

    def removeElement2(self, nums: List[int], val: int) -> int:
        L = 0
        '''
        移动特定元素
        双指针
        两个指针初始在同一位置，只有当右指针不满足条件了(遇到了需要往后替换的值)会相对于左指针向右一格
        然后左右指针的值进行替换就好了
        '''
        for R in range(len(nums)):
            # 右指针遇到需要替换的值，左指针不动，右指针向右移动（通过for循环增加1）
            # 若不是需要替换的值，则一起向右移动
            if nums[R] != val:
                nums[R], nums[L] = nums[L], nums[R]
                L += 1
        return len(nums[:L])

    def removeElement3(self, nums: List[int], val: int) -> int:
        """
        双指针优化
        """
        left, right = 0, len(nums)
        while left < right:
            if nums[left] == val:
                nums[left] = nums[right - 1]
                right -= 1
            else:
                left += 1
        return left

    def remove_element(self, nums: List[int], val: int) -> int:
        k = 0
        for num in nums:
            if num == val:
                continue
            nums[k] = num
            k += 1
        return k


if __name__ == '__main__':
    s = Solution()

    nums = [0, 1, 2, 2, 3, 0, 4, 2]  # 输入数组
    val = 2  # 要移除的值
    expectedNums = []
    aaaa = s.removeElement(nums, val)
    k = s.remove_element(nums, val)
    expectedNums[:] = nums  # 长度正确的预期答案

    assert k == len(expectedNums) - 1
    nums = sorted(nums[:k])

    # for i in range(len(expectedNums)):
    #     assert nums[i] == expectedNums[i]

    print("验证通过")
